package cn.xuchunh.sort;

import java.util.*;

public class QuickSort {
    public static void sort(int[] source, int start, int end) {
        if(source == null || source.length == 0) {
            return;
        }

        if(start >= end) {
            return ;
        }

        int pivot = source[start];
        int low = start;
        int high = end;
        while (low < high) {
            while (low < high && source[high] >= pivot) {
                high--;
            }
            if(low < high) {
                source[low++] = source[high];
            }

            while (low < high && source[low] <= pivot ) {
                low++;
            }
            if(low < high) {
                source[high--]  = source[low];
            }
        }
        source[low] = pivot;
        sort(source, start, low - 1);
        sort(source, low + 1, end);
    }

    public static void main(String[] args) {
        int[] array = new int[]{3,4,53,5621,52,52,52,542,16,6513,5,163,561,165,163,165,165};
        sort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ", ");
        }
    }
}
